This invention can relate to turbo codes. More particularly, this invention can relate to using early stopping rules with non-binary turbo codes.
Reliable and efficient transmission of data across potentially noisy channels is a key challenge in modern technology. To help achieve this goal, various encoding and decoding schemes have been developed, whereby the data to be transmitted is encoded with additional, redundant information. This redundancy can be examined at a receiving circuit to identify and, in some circumstances, correct errors that may have been introduced during transmission. After examining the received data in conjunction with the received redundancy, the receiving circuit can decode the data to generate a guess as to the value of the original unencoded data.
As an example, some well-known encoding techniques can include the use of checksums. A checksum can include one or more bits added to a data word, whose value is the modular sum of all the bits in that word or a portion of that word. Decoding circuitry at a receiving circuit can verify that the data stored in a given word is consistent with the checksum and take appropriate action if an error is detected.
Some encoding techniques permit not only detection, but also correction, of data errors introduced during transmission. For instance, multiple checksums can be applied to overlapping regions of a given data word. With this technique, a single-bit data error will generally result in two incorrect checksums, allowing identification of the corrupted bit. Moreover, one incorrect checksum can be interpreted as an error in the checksum itself, and not in any of the memory data bits. Checksums and similar redundancy-adding data that is generated during the encoding process shall be collectively referred to herein as “parity data,” while the original data to be encoded, transmitted, decoded, and checked shall be referred to herein as “systematic data.”
Another encoding technique that can be used to improve reliability of data transmission includes interleaving of data. This technique is based on the observation that data corruptions often occur in localized areas of a data stream, meaning blocks of consecutive bits are often corrupted together, making it relatively likely that a given corrupted data word will have several corrupted bits and create difficulty in effectively decoding the word. In order to lessen the chance that more than one bit will be inadvertently changed in a single data word, decoders often interleave the data bits by shifting them within the data stream such that the bits of any given word are no longer adjacent to each other, but rather are dispersed more widely. As such, receiver circuitry that decodes the received data can perform interleaving, de-interleaving, or both.
One category of encoding and decoding standards that has been developed is turbo codes. Turbo codes can be, for example, forward-error-correction codes that can be decoded by an iterative turbo decoder that can operate in a plurality of iterations. The data decoding can stop, for instance, after a certain maximum number of iterations has been performed. Traditional binary turbo codes, where data is represented with binary bits having only two possible values (logical “0” or logical “1”), can also apply early stopping rules when decoding received data. An early stopping rule can test for a certain condition at the end of each iteration and halt the decoding process when the condition is satisfied, even if the maximum number of decoding iterations has not yet been reached. Such early stopping rules can advantageously improve decoding speed, while sacrificing little or no accuracy in decoding.
Many systems today utilize non-binary turbo codes, where each unit of data is represented by a “symbol” with more than two possible values, rather than by a bit. Such non-binary turbo codes can be used, for instance, in the 802.16 transmission standard of the Institute of Electrical and Electronics Engineers (“IEEE”). One illustrative IEEE 802.16 standard that can be used in systems is the WiMax standard. Because non-binary turbo codes have, to date, not been as widely used as binary turbo codes, techniques for optimizing their efficiency and performance have not been as well-developed as those for binary turbo codes.